The section of a network which directly connects two nodes without including any other node is termed the link between those nodes. In most networks a node is connected by such direct links to only a few other nodes, these often being nodes which are spatially or geographically close to it.
When communication must be provided between any two nodes in a network to facilitate the transfer of data between them, a "route" must be provided between them. A request for a communication is usually made by a user located at one of the network's nodes who requests immediate provision of a route to one other single node in the network. The route assigned will consist of one or more links. There are usually very many possible routes between any two nodes, each of these routes passing through different sets of intermediate nodes and each therefore consisting of a different combination of links.
The problem which the present invention solves concerns selecting and assigning the optimum route for communication between any two nodes in a network. One aspect of this problem concerns exploiting the network's carrying capacity efficiently in the assignment of routes. Another aspect of this problem is the provision of the optimum route sufficiently quickly after a request is made that the user making the request does not have to wait and delay the planned communication significantly.
ATM networks which are presently used must respond to a request for the assignment of a route between any two nodes. This is done in some prior art networks by the following steps, or a variation thereof, performed in the order a)-c):
a) waiting until a request for a route is received. PA1 b) analyzing the nature of the request to decide which constraints are present, e.g. what is the bandwidth which the route must have. PA1 c) identifying which of the routes between the two nodes satisfying the constraints in the request should be assigned. This calculation usually seeks to minimize one parameter, e.g. the financial cost of the route, or the delay in the route. The result of this calculation is the optimum route for the particular request which was made. PA1 a) the constraints attached to the route request: PA1 b) how much of the network will be in use when the request is made, and therefore how much spare capacity each link in the network will actually have available when the real request is received. PA1 c) between which pair of nodes communication will be required. PA1 a) means for defining a first route characteristic to be optimized for a pair of selectable source and destination nodes; PA1 b) means for defining a minimum acceptable value of at least a second route characteristic; PA1 c) means for determining that route which is optimum with respect to said first route characteristic from amongst all routes between said pair of nodes which can be constructed using only links in the network having at least said minimum acceptable value of said second route characteristic, whereby the determination is repeated for successively higher minimum acceptable values of said second route characteristic; PA1 d) means for storing the optimum routes so determined; PA1 e) means which, upon receipt of a request for communication between said pair of source and destination nodes, choose the route which has the best value of said first route characteristic from amongst those routes stored for this pair of nodes which have at least the minimum value of said second route characteristic required by the request; and PA1 f) means for sending the communication to be transmitted along this chosen route. PA1 a) means which apply to the model of the system a so-called Spanning Tree Algorithm for finding the shortest spanning tree in terms of an additive route characteristic between said first node and each of said other nodes in the system; PA1 b) means for storing resulting routes if they are either strictly better than or not comparable to all previously stored routes, and discarding any previously stored routes which are strictly worse than said resulting routes; PA1 c) means for eliminating the first link, and any links equivalent to it, from said link list; PA1 d) means for removing from the model of the system the link or links removed from said link list; PA1 e) whereby the various means specified under a)-d) above are such as to repeat their said functions in the sequence a)-d) until there are no more links left on said link list. PA1 a) for a pair of selectable source and destination nodes, defining a first route characteristic to be optimized; PA1 b) defining a minimum acceptable value of at least a second route characteristic; PA1 c) determining that route which is optimum with respect to the said first route characteristic from amongst all routes between said pair of nodes which can be constructed using only links in the network having at least said minimum acceptable value of said second route characteristic; PA1 d) repeating step c) for successively higher minimum acceptable values of said second route characteristic; PA1 e) storing the optimum routes so determined; PA1 f) upon receipt of a request for communication between said pair of source and destination nodes, choosing the route which has the best value of said first route characteristic from amongst those routes stored for this pair of nodes which have at least the minimum value of said second route characteristic required by the request; and PA1 g) sending the communication to be transmitted along this chosen route. PA1 a) applying to the model of the system a so-called Spanning Tree Algorithm for finding the shortest spanning tree in terms of an additive route characteristic between said first node and each of said other nodes in the system; PA1 b) storing resulting routes if they are either strictly better than or not comparable to all previously stored routes, and discarding any previously stored routes which are strictly worse than said resulting routes; PA1 c) eliminating the first link, and any links equivalent to it, from said link list; PA1 d) removing from the model of the system the link or links removed from said link list; PA1 e) repeating steps a)-d) until there are no more links left on said link list. PA1 a) the delay of the signal within a link, the sum of the delays over the links of a route being that route's total delay and the route with the lowest total delay being the optimum route with respect to signal delay; PA1 b) the number of nodes existing along a route , the route with the lowest total number of nodes being the optimum route; PA1 c) the cost of transfer along a route, the route with the lowest total cost being the optimum route.
The calculations in step c) must be made for a very large number of possible routes.
Methods such as that given above are only usable for small networks where very few constraints can be made in the request. Typically only one constraint can be specified. If these conditions are not met then the calculation of which route to assign takes too much time for "real time" assignment of routes and is too expensive. For networks with very many links the calculation can become intractable, i.e. could not be completed within many years on even a very fast computer.
At least one prior art document has attempted to overcome these difficulties by performing the calculation mentioned above before the request for a route has been received. See the document "SNA Networks of Small Systems" from the IEEE Journal on Selected Areas in Communications discussed below. However, although by pre-calculating some or all of the routes there is effectively more time available in which to perform the calculation, the calculation itself becomes more complicated. This is because the following elements of the problem are not known before the request is submitted:
Therefore optimum route calculations need to be made for various hypothetical constraints, load factors and pairs of nodes which might be applicable to a future request.
No prior art method has offered an affordable and complete solution to carry out these calculations for real networks of the kind which will be encountered in ATM communications systems.
The following are known prior art systems where route assignment is necessary or is described:
IEEE INFOCOM '92, pages 2A.2.1-2A.2.6 (0153-0158) by M. AIDA et al.: "Optimal routing in communication networks with delay variations". This paper adopts a statistical approach to minimizing the path delay. The mean and variance of path delay are plotted graphically, and an algorithm is applied to these values in order to find the optimum path.
IEEE Journal on Selected Areas in Communications, vol. SAC-3, No. 3, May 1985, pages 416-426 by A. E. BARATZ et al.: "SNA Networks of Small Systems". This article describes route selection in terms of calculation of the optimum route from one node to every other node in the network. The selection leads to each node holding a database of optimum routes to all the other nodes for certain "classes" of service. In determining these optimum routes, each link in the network is considered to have multivalued properties, e.g. bandwidth or delay. These properties are used to determine the suitability of a link for a particular class of service. This is done using "weights" assigned to each link, where the value of the weight is a measure of the suitability of the link for the class of service under consideration and the value of the weight is set at zero for a link which is inappropriate for that class of service. A single class of service weight is assigned to each link or node to cover all its characteristics, with the result that the optimum route calculation lacks the precision of the method of the present invention. This lack of rigorousness may lead the method to miss a satisfactory route when one in fact exists. There is no attempt to exhaustively derive the set of optimum routes for all possible values of route constraints.
U.S. Pat. No. 5,088,032 concerns routing communications in a computer network. A metric is calculated for a possible route which depends, e.g. on the delay and the inverse of the bandwidth of links in the route. Other characteristics can be included in this metric, depending on the characteristics required of the route. In fact, the metric assigns a measure of relative importance to each of the requirements of a communication, such as high bandwidth, low delay or high reliability. Minimization of this metric to select the optimum route therefore is not mathematically rigorous, i.e. it does not lead with certainty to the optimum route and is an approximation. Furthermore, the metric is used as the basis for deliberately splitting traffic amongst several paths through the network in dependence on the value of the metric, and thus teaches away from the single route solution employed in the present application.
EP-A-0 398 614 discloses a method of routing data within a network. Lists of the optimal "next link" for any final destination node are compiled for each positive attribute, e.g. an entry on one list states which link should be chosen if starting from the present node, wanting to communicate with a particular final destination node and being interested in minimizing hop count. These lists do not correspond to those of the present invention, where entire optimum routes are stored after a process of route selection. The method of EP-A-0 398 614 furthermore aims only to deal with the decision as to which node to use next from the node which a communication has currently reached, rather than determining the entire route before beginning transmission. This incremental approach leads away from the idea of a pre-calculation of complete optimum routes and then sorting these routes as is achieved by the present invention. EP-A-0 398 614 also envisages sending the control information relating to the data being transmitted over a different path than that used for the data itself.
U.S. Pat. No. 5,317,566, published on May 31, 1994, offers a recent solution to the problem of route selection in a network. On receipt of a first route request, a least cost route is calculated and assigned. This route is then held in memory together with the transmission requirements from the route request. When, later, a further request for a route to the same destination is received, the transmission requirements of that request are compared with those stored. If they match, then the stored route is assigned in response to the new request.
The solution offered by U.S. Pat. No. 5,317,566 starts from the premise that time can be saved in route assignment by storing the last route used, because the transmission requirements of a route request are likely to be the same as those of the previous route request. This solution leads to the route held in memory not being of use if successive route requests have different transmission requirements. Furthermore, no thorough pre-calculation and sorting of a set of optimum routes is carried out.
In a further development, the arrangement of U.S. Pat. No. 5,317,566 calculates a second "next best" route at the time of calculating the least cost route, and stores this together with the least cost route actually used. If any link of the stored least cost route is unavailable at the time of receipt of a later route request with the same transmission requirements, then this next best route can be assigned. This aspect of the arrangement of U.S. Pat. No. 5,317,566 teaches away from the arrangement of the invention of the present application.